"""
author：fc
date：  2021/10/17
"""
#
# 手动决策树的实现
#

import operator
import math


class DecisionTree:
    def __init__(self):
        pass

     #加载数据集
    def loadData(self):
        """
        天气：0：雨，   1：阴，2：晴
        温度：0：寒冷， 1：适中，2：炎热
        湿度：0：正常， 1:高
        风速：0：弱，  1：强
        :return:
        """
        features = ['天气', '温度', '湿度', '风速']
        data = [
            [2, 2, 1, 0, "yes"],
            [2, 2, 1, 1, "no"],
            [1, 2, 1, 0, "yes"],
            [0, 0, 0, 0, "yes"],
            [0, 0, 0, 1, "no"],
            [1, 0, 0, 1, "yes"],
            [2, 1, 1, 0, "no"],
            [2, 0, 0, 0, "yes"],
            [0, 1, 0, 0, "yes"],
            [2, 1, 0, 1, "yes"],
            [1, 2, 0, 0, "no"],
            [0, 1, 1, 1, "no"],
        ]
        return data, features

    # 计算数据集的香农熵
    def ShannonEnt(self,data):
        numData=len(data) # 求长度
        labelCounts = {}
        for feature in data:
            onaLabel = feature[-1] # 获取标签
            labelCounts.setdefault(onaLabel,0)   # 如果标签不在新定义的字典里，则创建该标签值
            # 该类标签下含有的数据个数
            labelCounts[onaLabel]+=1
        shannonEnt=0.0
        for key in labelCounts:
            prob = float(labelCounts[key])/numData #同类标签出现的概率
            shannonEnt -=  prob * math.log(prob) # -∑ p*log2(p)
        return shannonEnt

    # 计算每个属性的信息增益g g=E(D)-E(D|A)，其中E(D)为属性的信息熵，E(D|A)为特征值=A分割数据后的信息熵
    # 返回信息增益最大的属性
    def splitData(self,data,axis,value):
        """

        :param data: 数据集
        :param axis: 划分数据集的特征
        :param value: 特征的返回值
        :return:
        """
        retData=[]
        for feature in data:
            if feature[axis] == value:
                reducedFeature=feature[:axis]
                reducedFeature.extend(feature[axis+1:])
                retData.append(reducedFeature)
        return retData # 返回一个列表

    # 选择最好的数据集划分方式
    def chooseBestFeatureToSplit(self,data):
        numFeature=len(data[0])-1
        baseEntropy= self.ShannonEnt(data)
        bestInfoGain=0.0
        bestFeature=-1
        for i in range(numFeature):
            # 获取第i个特征值所有的可能值
            featureList = [result[i] for result in data]
            # 从列表中创建集合，得到不重复的所有可能取值
            uniqueFeatureList=set(featureList)
            newEntropy =0.0
            for value in uniqueFeatureList:
                # 以i为数据特征，value为返回值，划分数据集
                splitDataSet=self.splitData(data,i,value)
                #数据集特征为i的数据集所占的比例
                prob = len(splitDataSet)/float(len(data))
                # 计算每种数据集的信息熵
                newEntropy +=prob*self.ShannonEnt(splitDataSet)
            infoGain=baseEntropy-newEntropy
            if infoGain>bestInfoGain:
                bestInfoGain=infoGain
                bestFeature=i
        return bestFeature

    # 递归构建决策树
    def majorityCnt(sel,labelsList):
        labelsCount={}
        for vote in labelsList:
            if vote not in labelsCount.keys():
                labelsCount[vote]=0
            labelsCount[vote]+=1
        sortedLabelsCount=sorted(
            labelsCount.iteritems(),key=operator.itemgetter(1),reverse=True
        ) # 升序排序
        print(sortedLabelsCount)
        return sortedLabelsCount[0][0] #返回出现次数最多的

    # 创建决策树
    def createTree(self,data,features):
        features=list(features)
        labelsList=[line[-1] for line in data]
        # 类别完全相同的停止划分
        if labelsList.count(labelsList[0])==len(labelsList):
            return labelsList[0]
        # 遍历完所有特征值时返回出现次数最多的
        if len(data[0])==1:
            return self.majorityCnt(labelsList)
        # 选择最好的数据集划分方式
        bestFeature=self.chooseBestFeatureToSplit(data)
        bestFeatLabel=features[bestFeature] # 得到对应的标签值
        myTree= {bestFeatLabel:{}}
        # 清空 features[bestFeatures]，在下一次使用时清零
        del (features[bestFeature])
        featureValues=[example[bestFeature] for example in data]
        uniqueFeatureValues=set(featureValues)
        for value in uniqueFeatureValues:
            subFeatures=features[:]
            #递归调用创建决策树函数
            myTree[bestFeatLabel][value]=self.createTree(
                self.splitData(data,bestFeature,value),subFeatures
            )
        return  myTree
    # 新数据预测是否举办活动
    def predict(self,tree,features,x):
        for key1 in tree.keys():
            secondDict=tree[key1]
            # key是根节点代表的象征， # featIndex是取根节点特征在特征列表中的索引，方便后面对输入样本逐变量判断
            featIndex=features.index(key1)
            # 这里的每一个key值对应的是根节点特征的不同的取值
            for key2 in secondDict.keys():
                # 找到输入样本在决策树中由根节点往下走的路径
                if x[featIndex]==key2:
                   # 该分支产生了一个内部节点，则在决策树中继续用同样的操作查找路径
                   if type(secondDict[key2]).__name__=="dict":
                      classLabel=self.predict(secondDict[key2],features,x)
                   # 该分支产生的是叶节点，直接取值就能得到类别
                   else:
                       classLabel =secondDict[key2]
        return classLabel

if __name__ == '__main__':
    dtree=DecisionTree()
    data,features=dtree.loadData()
    myTree=dtree.createTree(data,features)
    print(myTree)
    label=dtree.predict(myTree,features,[1,1,1,0]) # 预测天气：阴，温度适中，湿度：高，风速：若是否举办活动
    print("新数据[1,1,1,0]对应的是否要举办活动为{}".format(label))